ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpa/3nmas1/main.cpp

   1 #include <stdio.h>
   2 #include <iostream>
   3 #include <vector>
   4 using namespace std;
   5
   6 typedef unsigned int uint;
   7 typedef unsigned short ushort;
   8
   9 #define Max_memo        1000001
  10 vector<ushort> d(Max_memo, 0);
  11
  12 #define memorizado(x)   ((x) < Max_memo && d[(x)] != 0)
  13 #define next(n) ((n) % 2 == 0 ? (n) / 2 : 3 * (n) + 1)
  14
  15 ushort periodo(uint n) {
  16         if (memorizado(n)) {
  17                 return d[n];
  18         } else {
  19                 ushort p = periodo(next(n)) + 1;
  20                 if (n < Max_memo) {
  21                         d[n] = p;
  22                 }
  23                 return p;
  24         }
  25 }
  26
  27 ushort resolver(uint x, uint y){
  28         ushort res = 0;
  29         uint i = min(x,y);
  30         uint sup = max(x,y);
  31         ushort aux;
  32         i = max(sup/2,i);
  33
  34         while(i <= sup){
  35                 aux = periodo(i);
  36                 if (aux > res){
  37                         res = aux;
  38                 }
  39                 i++;
  40         }
  41         return res;
  42 }
  43
  44 int main(int argc, char **argv)
  45 {
  46         uint x, y;
  47         d[1] = 1;
  48         while (scanf("%u %u",&x,&y)==2) {
  49                 cout << x <<" "<< y <<" " << resolver(x, y) << endl;
  50         }
  51         return 0;
  52 }
  53